#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <iostream>
#include <cstdlib>
using namespace std;

template <typename Comparable>
class BinarySearchTree
{
public:
	// The 3 methods
	BinarySearchTree()
	{
		root = NULL;
	}
	BinarySearchTree(const BinarySearchTree & rhs)
	{
		makeEmpty(root);
		root = clone(rhs.root);
	}
	~BinarySearchTree()
	{
		makeEmpty(root);
	}

	const Comparable & finMin() const;
	const Comparable & finMax() const;
	bool contains(const Comparable &x) const
	{
		return contains(x, root);
	}
	bool isEmpty() const;
	void printTree() const;

	void makeEmpty();
	void insert(const Comparable& x)
	{
		insert(x, root);
	}
	void remove(const Comparable& x)
	{
		remove(x, root);
	}
	const BinarySearchTree& operator = (const BinarySearchTree & rhs);

private:
	struct BinaryNode
	{
		Comparable element; 
		BinaryNode *left;
		BinaryNode *right;

		BinaryNode(const Comparable &theElement, BinaryNode * lt, BinaryNode *rt)
			:element(theElement), left(lt), right(rt){}
	};
	BinaryNode *root; 
	
	void insert(const Comparable& x, BinaryNode* &t) 
	{
		if (t ==NULL)
		{
			t= new BinaryNode(x,NULL,NULL);
		}
		else if (x < t->element)
		{
			insert(x, t->left);
		}else if (x > t->element)
		{
			insert(x,t->right);
		}
		else
			;//Duplicate, Do nothing 
	}
	void remove(const Comparable& x, BinaryNode* &t) 
	{
		if (t == NULL)
		{
			return;
		}
		if (x < t->element)
		{
			remove(x,t->left);
		}else if(x > t->element)
		{
			remove(x, t->right);
		}else if (t->left != =NULL && t->right!=NULL) // x equals current node, and current has 2 children
		{
			t->element = findMin(t->right)->element;
			remove(t->element,t->right);
		}else{//x equals current node, and only 1 child exists 
			BinaryNode *oldNode = t;
			t = (t->left !=NULL) ? t->left : t->right;
			delete oldNode;
		}

	}
	BinaryNode * finMin(BinaryNode *t) const
	{
		if (t ==NULL )
		{
			return NULL;
		}
		if(t->left==NULL){
			return t;
		}
		return t->left;
		
	}
	BinaryNode * finMax(BinaryNode *t) const
	{
		if (t ==NULL )
		{
			return NULL;
		}
		if(t->right==NULL){
			return t;
		}
		return t->right;
	}

	bool contains(const Comparable& x, BinaryNode* &t)
	{
		if (t ==NULL)
		{
			return false;
		}else if (x < t->element)
		{
			return contains(x, t->left);
		}else if (x > t->element)
		{
			return contains(x, t->right);
		}else
		{
			return true;
		}

	}
	void makeEmpty(BinaryNode * &t)
	{
		if (t != NULL)
		{
			makeEmpty(t->right);
			makeEmpty(t->left);
			delete t;
		}
		t = NULL;
	}
	void printTree(BinaryNode* t ) const
	{
		cout<< t->element;
	}
	BinaryNode* clone(BinaryNode *t) const
	{
		if (t == NULL)
		{
			return NULL
		}
		return new BinaryNode(t->element, clone(t->left), clone(t->right));
	}
};


#endif